#include <stdio.h>
#include <stdlib.h>

typedef int ElemType_Tree;

// 定义一个链表数据结构
typedef struct LNode{
    ElemType_Tree data;
    struct LNode *next;
}LNode, *LinkList;

// 初始化一个带头结点的单链表
void initLinkListWithHeadPointer(LinkList &L) {
    L = (LinkList) malloc(sizeof (LNode));
    L->data = NULL;
    L->next = NULL;
}

// 打印链表（指定方法）
void PrintList(LinkList L) {
    L = L->next;
    while (L != NULL) {
        printf("%3d", L->data);//打印当前结点数据
        L = L->next;//指向下一个结点
    }
    printf("\n");
}

// 尾插法新建链表
LinkList createLinkListByTail(LinkList &L) {
    // r指向链表表尾
    LinkList s, r = L;
    ElemType_Tree e;
    scanf("%d", &e);
    while (e != 9999) {
        s = (LinkList) malloc(sizeof (LNode));
        s->data = e;
        s->next = NULL;
        r->next = s;
        r = s;
        scanf("%d", &e);
    }
    return L;
}

// 在指定位置插入元素
bool LinkListInsertElem(LinkList L, int pos, ElemType_Tree e) {
    LinkList tmp;
    int i = 0;          // i表示当前指针所在的结点位置
    while (L->next != NULL && i < pos) {
        tmp = L;        // 记录前一个结点的位置
        L = L->next;
        i++;
    }
    // 判断查询位置是否合法
    if (i != pos) {
        return false;
    }

    // 为新结点申请空间
    LinkList p = (LinkList) malloc(sizeof (LNode));
    p->data = e;
    p->next = tmp->next;
    tmp->next = p;
    return true;
}

// 删除指定位置的元素，返回被删除的元素值
ElemType_Tree LinkListDelElemByPos(LinkList L, int pos) {
    LinkList tmp;
    ElemType_Tree e = NULL;  // 存放被删除的元素值
    int i = 0;          // i表示当前指针所在结点位置
    while (L->next != NULL && i < pos) {
        tmp = L;        // 记录前一个结点的位置
        L = L->next;
        i++;
    }
    // 判断删除位置是否合法
    if (i != pos) {
        return e;
    }

    // 删除元素操作
    tmp->next = L->next;
    e = L->data;
    free(L);
    return e;

}

// 按位查找元素
ElemType_Tree LinkListGetElemByPos(LinkList L, int pos) {
    int i = 0;  // i表示当前指针所在的结点位置
    while (L->next != NULL && i < pos) {
        L = L->next;
        i++;
    }
    // 判断查询位置是否合法
    if (i != pos) {
        return NULL;
    }
    return L->data;
}

/**
 * 输入3 4 5 6 7 9999一串整数，9999代表结束，通过尾插法新建链表，查找第二个位置的值并输出，
 * 在2个位置插入99，输出为  3 99  4  5  6  7，删除第4个位置的值，打印输出为  3 99  4  5  6  7。
 *
 * 输出函数如下：
 *      void PrintList(LinkList L) {
 *          L = L->next;
 *          while (L != NULL) {
 *              printf("%3d", L->data);//打印当前结点数据
 *              L = L->next;//指向下一个结点
 *          }
 *          printf("\n");
 *      }
 *
 * 针对双向链表，有时间的同学自己练习即可，这道题同样也可以用双向链表来实现一遍
 * // TODO：链表的插入/删除的实现逻辑有待改进，通过 pos-1 直接查到指定位置的前一个结点即可
 * @return
 */
int main() {
    // 初始化一个带头结点的单链表
    LinkList L;
    initLinkListWithHeadPointer(L);
    // 尾插法插入一串整数
    createLinkListByTail(L);
//    PrintList(L);

    // 查找第2个位置的值，并输出
    ElemType_Tree e_search = LinkListGetElemByPos(L, 2);
    printf("%d\n", e_search);

    // 在第2个位置插入元素，并输出当前链表
    if (LinkListInsertElem(L, 2, 99)) {
        PrintList(L);
    } else {
        printf("插入元素失败..\n");
    }

    // 删除第4个位置的元素，并输出当前链表
    ElemType_Tree  e_delete = LinkListDelElemByPos(L, 4);
    PrintList(L);

    return 0;
}